DAY 24 試題

問題描述

給定一個由不同整數組成的陣列 candidates 和一個目標整數 target，返回所有數字組合的清單，使得每組數字的和等於 target。在每個組合中，同一個數字可以被選擇多次。每組數字的頻率至少有一個數字不同的組合會被視為獨立的組合。

輸入保證在給定的條件下，不同組合的數量會少於 150。

範例 1：

• 輸入：candidates = [2,3,6,7]，target = 7
• 輸出：[[2,2,3], [7]]
• 解釋：
  • 數字 2 和 3 可以被選擇並且 2 + 2 + 3 = 7。
  • 數字 7 自身就是一個符合條件的組合。

範例 2：

• 輸入：candidates = [2,3,5]，target = 8
• 輸出：[[2,2,2,2], [2,3,3], [3,5]]

範例 3：

• 輸入：candidates = [2]，target = 1
• 輸出：[]
• 解釋：目標值 1 小於唯一的候選數字 2，因此無法形成組合。

解題思路

這個問題可以用 回溯法 來解決。回溯法的核心在於逐步探索所有可能的組合，當發現一個符合條件的組合後將其記錄，否則回退並繼續嘗試其他可能。
詳細步驟：

1. 排序：我們首先對 candidates 進行排序，這樣可以避免不必要的重複計算。

2. 回溯法：

• 從 candidates 中的每個數字開始，逐步嘗試將該數字加入當前的組合。
• 如果當前的數字加總超過了 target，則停止嘗試並返回上一層。
• 如果加總恰好等於 target，則將當前的組合加入結果中。
• 每次遞迴可以選擇相同的數字（因為每個數字可以重複使用）。

3. 剪枝：當目前的總和已經超過 target 時，直接停止當前分支的計算，這樣可以提高效率。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current_combination;
        backtrack(candidates, target, 0, current_combination, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& candidates, int target, int start, vector<int>& current_combination, vector<vector<int>>& result) {
        // 若目標為 0，則表示找到一個有效的組合
        if (target == 0) {
            result.push_back(current_combination);
            return;
        }
        
        // 遍歷候選數字
        for (int i = start; i < candidates.size(); i++) {
            // 若當前數字超過目標，則跳過這個分支
            if (candidates[i] > target) continue;
            
            // 選擇當前數字，並加入當前組合
            current_combination.push_back(candidates[i]);
            
            // 由於數字可以重複使用，因此遞迴時，依然從當前索引開始
            backtrack(candidates, target - candidates[i], i, current_combination, result);
            
            // 回溯，移除當前數字
            current_combination.pop_back();
        }
    }
};

解法重點與分析

1. 回溯法與遞迴：本題是經典的回溯法問題，藉由遞迴不斷嘗試不同的數字組合，並在找到符合條件的組合時將其記錄。透過回溯，我們可以探索所有可能的數字組合，並在每次不符合條件時退回上一步。
2. 避免重複使用相同組合：由於可以重複使用數字，但我們使用相同的起始索引來遞迴，確保每次都是從當前數字或更後的數字開始，這樣可以避免重複的組合。
3. 剪枝：當目前數字大於目標值時，我們可以立即跳過這個分支，這樣避免了不必要的計算。
4. 時間複雜度：最差情況下會遍歷所有可能的組合，這使得時間複雜度為指數級別，即 O(2^n)，其中 n 是候選數字的數量。
5. 空間複雜度：遞迴過程中使用的空間與遞迴深度相關，最差情況下為 O(target / min(candidates))。

總結

此題的關鍵在於運用回溯法來探索所有可能的數字組合，並透過剪枝技術提高計算效率。在找到每組符合條件的組合後，我們將結果返回，這樣可以解決多個不同數字組合的問題。

以上是第二十四天的自學內容分享，謝謝大家。